1. Field of the Invention
The present invention relates to a figure filling device applied to display units and printers and particularly relates to a figure filling device capable of pasting arbitrary tiling patterns in so-called "scan line fill" processing where scanned lines on the memory defined by X-Y coordinates are filled one by one.
2. Description of the Prior Art
In recent years, software for attractive presentation for use on office automation machines such as personal computers, word processors and workstations has become available. Such software not only expresses characters, graphs and tables but also more complicatedly shaped figures on the display screen. When such displayed images are printed, all figures are represented as polygons with their internal areas filled, since printers usually have much higher resolution--several times the resolution of display units. Specifically, a line having a width of one pixel is too thin to use because of high resolution, and it is necessary to always use thick lines or squares as processing units. There are several methods to fill the inside of polygons including squares, but any method requires scan line fill at the last stage. Therefore, the throughput of the entire system largely depends on the speed of the scan line fill processing.
Conventional software as described above is capable of filling figures not only with a single color but also with arbitrarily tiling patterns by referring them. A tiling pattern is a rectangular pattern with a certain size placed like a tile to fill the area subjected to fill processing. To keep proper continuance of patterns, it is necessary to sequentially determine the location to be referred to in the tiling pattern when performing scan line fill.
Conventional methods to determine the pattern reference location are described here. One of such methods limits the tiling patterns to those with 16.times.16 or 32.times.32 pixels for simple processing. For example, suppose 16 bits constitute one word and 16.times.16 pixels make a tiling pattern in a monochrome device treating one pixel as one bit. In this case, regardless of the X coordinate of the start point of the scan line, the same word data is always used for horizontal direction. It is necessary to determine firstly which of the 16 word data in the Y direction is to be selected, but this can be decided by the lower four bits of the Y coordinate of the start point, and the calculation is quite simple.
In another method where tiling patterns can be of any size, the processing becomes quite troublesome. Firstly, it is required to determine the point on the tiling pattern to which the drawing start point of the scan line corresponds. The X coordinate of the drawing start point is divided by the vertical width of the tiling pattern to obtain the remainder, which is used as the X coordinate on the pattern. Then, the Y coordinate of the drawing start point is divided by the height of the tiling pattern to obtain the remainder, which is used as the Y coordinate on the pattern. This means that two divisions are required. Divisions are generally performed by a restoring method. In this method, the dividend and the divisor are aligned for the number of digits first, and the divisor is shifted to the left one bit by one bit to obtain the number of shifts required until the divisor exceeds the dividend. Then, with shifting the divisor to the right, the dividend is subjected to subtraction. If the result is negative, the divisor is added again. The value left after such shifting and subtraction repeated for the number of shifts as determined above is the remainder.
As mentioned above, recent software programs feature desk top publishing, desk top presentation or other similar functions and are capable of fine and beautiful drawing. Naturally, any size of tiling patterns can be defined in such programs. Therefore, it is required to improve the speed of scan line fill processing. In addition, with WYSIWYG (What you see is what you get) becoming popular, it is desired that the image on the display screen and the image provided by the printer give the same impression. To obtain the same impression image irrespective of the resolution of the printing device such as a printer, the resolution can be arbitrarily changed. It is required to change the size of the filing pattern in addition to the conversion of the coordinate data for the figure in order to obtain the same image using different devices with different resolutions. Therefore, it is now becoming more important to fill the figures using arbitrary tiling patterns.
In an application of scan line fill, scan lines each having a length of some dots are continuously drawn (for filling). A typical example is the outline font where the outline of a character is expressed with straight and curved lines and the coordinates of those segments are kept as the original information. The outline font is now becoming popular as one of the basic functions for word processors. Drawing in the outline font function is deemed to be filling of polygons, and can be reduced to the drawing for each of the horizontal lines, or in other words, the scan line fill. Since a character usually has a size of 60 dots.times.60 dots approximately, it is easily understood that the number of dots continuously existing on a single scan line is often several dots. Further, in division into scan lines, adjacent segments are continuously generated. The segment filling processing itself requires only a short time since each segment has only a dozen dots at most. Therefore, the essential point in such application is the speed of calculation to determine the reference start point of the filling pattern. When the conventional method is used to determine the remainder, it takes time in proportion to the number of significant digits of the dividend and the divisor; this means that even when the filling itself requires only a few clocks, determination of the pattern reference start point needs some tens of clocks, resulting in lengthy processing time.